<?php
/**
 * @title 1631. 最小体力消耗路径 - 递归 + 剪枝
 * @author start2004
 */

ini_set("memory_limit", "128M");

// class Solution {
//
//     function find() {
//
//     }
// }


class Solution {

    /**
     * @param Integer[][] $heights
     * @return Integer
     */
    function minimumEffortPath($heights) {
        /**
         * @since 2020-10-26 宽, 高
         */
        $this->w = count($heights[0]);
        $this->h = count($heights);

        /**
         * @since 2020-10-26 最省体力
         */
        $this->result = PHP_INT_MAX;

        /**
         * @since 2020-10-26 每个方块, 最省体力值
         */
        $this->heights = array_fill(0, $this->h, array_fill(0, $this->w, PHP_INT_MAX));

        /**
         * @since 2020-10-26 暴力递归
         */
        $sH = $heights[0][0];
        $heights[0][0] = null;
        self::find($sH, 0, 0, 0, $heights);

        /**
         * @return
         */
        return $this->result;
    }

    /**
     * @title 递归每条路线
     * @author start2004
     * @since 2020-10-26 Created
     *
     * @param int $sH
     * @param int $i
     * @param int $j
     * @param int $max
     * @param array $heights
     * @return int|mixed
     */
    public function find($sH = 0, $i = 0, $j = 0, $max = 0, $heights = []){
        /**
         * @since 2020-10-26 到达终点
         */
        if($i == $this->h-1 AND $j == $this->w-1){
            if($max < $this->result){
                $this->result = $max;
            } else {}
        } else {}

        /**
         * @since 2020-10-26 已经超过最大体力值, 不需要计算了
         */
        if($max >= $this->result){
            return false;
        } else {}

        /**
         * @since 2020-10-26 当前方格消耗最大体力值
         */
        if($max >= $this->heights[$i][$j]) {
            return false;
        } else {
            $this->heights[$i][$j] = $max;
        }

        /**
         * @since 2020-10-26 消耗体力
         */
        $result = PHP_INT_MAX;

        /**
         * @since 2020-10-26 向上
         */
        if($i>=1 AND ($eH=$heights[$i-1][$j]) !== null){
            $max1 = max($max, abs($sH-$eH));
            $heights[$i-1][$j] = null;
            self::find($eH, $i-1, $j, $max1, $heights);
            $heights[$i-1][$j] = $eH;
        } else {}

        /**
         * @since 2020-10-26 向下
         */
        if($i <= $this->h-2 AND ($eH=$heights[$i+1][$j]) !== null){
            $max1 = max($max, abs($sH-$eH));
            $heights[$i+1][$j] = null;
            self::find($eH, $i+1, $j, $max1, $heights);
            $heights[$i+1][$j] = $eH;
        }

        /**
         * @since 2020-10-26 向左
         */
        if($j>=1 AND ($eH=$heights[$i][$j-1]) !== null){
            $max1 = max($max, abs($sH-$eH));
            $heights[$i][$j-1] = null;
            self::find($eH, $i, $j-1, $max1, $heights);
            $heights[$i][$j-1] = $eH;
        }

        /**
         * @since 2020-10-26 向右
         */
        if($j<=$this->w-2 AND ($eH=$heights[$i][$j+1]) !== null){
            $max1 = max($max, abs($sH-$eH));
            $heights[$i][$j+1] = null;
            self::find($eH, $i, $j+1, $max1, $heights);
            // $heights[$i][$j+1] = $eH;
        } else {}

        /**
         * @return
         */
        return $result;
    }
}


/**
 * @url http://127.0.0.1/leetcode/202010/2020.10.26_4.php
 */
$datas = [
    [[[1,2,2],[3,8,2],[5,3,5]]], // 2
    // [[[1,2,3],[3,8,4],[5,3,5]]], // 1
    // [[[1,2,1,1,1],[1,2,1,2,1],[1,2,1,2,1],[1,2,1,2,1],[1,1,1,2,1]]], // 0
    // [[[4,3,4,10,5,5,9,2],[10,8,2,10,9,7,5,6],[5,8,10,10,10,7,4,2],[5,1,3,1,1,3,1,9],[6,4,10,6,10,9,4,6]]], // 5
    // [[[826373,114459,456893,830673,493660,349029,730446,282010,110722,351152,207609,79973,693628,877025,908543,327553,633714,201752,870936,936048,445946,344657,576780,688419,226436,188750,175810,378863,167567,316553,800421,899300,968931,748698,644920,982897,251850,603005,643612,368406,458856,520367,245157,17634,341969,643325,33736,599132,6979,922779],[444915,535098,378342,84816,357445,458802,605505,370926,424909,541163,685168,790870,552599,271276,395887,634836,411380,517444,292351,924941,41421,317391,589869,276905,513084,684625,323422,407688,875572,194162,577742,796181,367379,804264,104448,548460,591353,126668,625113,277978,25686,363279,382745,40716,929773,544497,14911,82518,754733,89892],[558172,332613,396713,347398,236031,70080,6462,741889,220154,483628,201731,254131,834170,89606,971075,580972,909994,404214,258482,367056,14389,79587,569993,55174,136736,77856,475505,354961,137403,570918,18571,257127,440074,887036,683323,436575,518078,135150,686622,332732,576527,725080,296796,758433,17040,419377,912700,198019,335110,424624],[298484,421352,404027,119501,326583,475916,272515,97351,37010,80706,588587,634067,73086,150141,127325,533878,800946,592538,323101,288051,990316,944649,12869,833756,994089,381630,498501,630830,941562,954842,324474,161099,903953,821715,999651,589262,37775,903326,807830,261577,334911,352562,853401,292653,689543,284380,480487,551349,628320,403713],[640784,416242,595598,527508,790464,381685,181230,24266,88496,159961,66391,227537,281253,8878,741209,575703,828476,79199,165794,419053,289458,205415,507609,141572,401453,899980,686502,28802,203525,157731,745356,584233,80083,25129,723585,733381,415519,337793,655379,965125,389703,179578,604811,857658,279598,401258,211190,510765,582930,163247],[8631,921767,820818,80596,409935,232427,279153,210258,808973,631245,895941,752150,183768,495375,876409,120819,563735,293337,307784,851410,7039,51366,723901,116885,236847,672317,377824,468278,545603,89945,774003,767418,801590,79375,939006,316364,935845,198346,733503,416920,286313,778113,893219,944444,410306,19659,423839,239914,383200,303465],[112301,356994,435601,693449,769572,825406,284062,177559,508259,829523,561880,898393,766044,267023,733822,559931,83588,23240,766773,580595,739908,851929,874520,551636,883574,599791,968247,893253,17102,950412,188663,833136,191211,319190,985201,693061,724195,682842,789705,767210,314674,100813,416663,861414,150202,420694,71846,653366,62667,366399],[476785,668485,86067,774934,359377,856908,584167,440015,861402,932043,83877,979715,104074,30252,188813,245675,904818,645888,138493,474387,964739,821252,494392,326088,419878,393941,799028,139559,457252,463854,438608,239151,700752,539256,389120,311177,794861,711899,490632,46682,263967,543360,63890,540382,590336,100270,81893,518798,583115,624939],[562915,523117,17820,127869,18850,316849,987702,497114,76159,698928,507463,498829,759280,307206,321958,935528,66327,632259,939637,131717,51401,394312,599569,464774,159034,163846,861986,888959,816930,483458,237516,872342,909340,247660,620237,502585,141821,611864,777932,453667,876694,616532,544470,452044,952007,842981,136770,511798,723445,931077],[317581,313597,558944,657848,542214,982586,224829,772771,973085,868940,317769,179195,685405,530165,699524,276793,652676,36301,969910,130367,280157,166029,933662,798495,22820,841606,499386,281572,603765,65194,650921,739311,131829,231796,311401,95808,185965,102876,305843,567273,365875,931606,859334,560432,493852,47069,382148,632844,371424,282394],[403842,911693,569558,675714,445389,517659,256294,885037,432633,392169,36900,783076,777701,716894,522178,432648,636547,14885,662028,352348,865475,43553,76843,423310,307494,309994,195352,875005,402044,680219,5535,414391,129703,965958,266525,634138,620082,475134,139341,23854,952258,468847,336917,71645,890119,925361,716624,535911,791485,966496],[874963,200884,369188,331721,190720,378874,374846,642823,582054,92805,523995,157371,574158,822986,573845,630911,305541,433577,246079,942084,809242,333192,458977,51288,689906,143331,667240,245896,1240,924969,294378,452031,468114,945467,611980,842513,748992,70087,401683,764956,467913,979395,394510,441278,837164,293143,681425,693276,891580,886679],[685217,988151,88539,83001,336982,223755,6422,518312,942933,255488,101161,896690,926954,431900,757347,614887,700853,243540,951876,206318,568339,240339,338583,802240,455772,78425,153507,757902,636994,962794,801689,883656,421643,601505,991144,130877,301444,521815,346634,895119,990431,394120,461715,940264,244091,189573,759426,777109,645758,419773],[207806,262849,850635,34551,504403,153749,187132,916858,470354,400492,418508,417694,650449,957589,280234,767138,654299,842524,479165,672684,944348,528422,403358,542318,163475,637355,902128,754089,828239,266474,23898,831692,783290,114980,697403,47202,589726,791953,273833,964190,569858,222816,116306,363249,720862,58,917075,296302,51809,963098],[169371,972264,709042,260396,25429,125026,879481,43875,607028,236293,193742,852600,223044,217717,385509,901833,309492,318008,823004,300753,842645,832641,939886,270175,866795,80173,698964,183952,287049,788396,330829,48524,42310,756170,719619,317115,667397,901143,775800,786546,659204,895423,304362,586422,613397,869690,971702,373587,534599,637755],[397723,525151,144362,416332,949744,749111,89261,620828,71163,199312,610651,122166,172814,624068,554331,15331,598317,554260,266009,234835,462960,648346,539544,490442,239115,131386,178026,678863,945255,816116,413133,927891,122905,345576,168784,974568,703824,194453,259711,622806,926545,369789,781277,360864,719639,730789,625675,46807,442198,669956],[222430,221298,898830,759118,381649,530369,749699,27518,765322,441961,536733,823618,436028,972568,918580,424183,995595,447285,122964,666029,505340,917455,358847,762984,579827,61895,449604,691990,580172,308255,950323,20999,330678,57755,715900,896672,680853,508817,234124,206442,442872,989987,272684,633832,90169,405268,341072,342331,835261,332667],[265759,537781,193252,522992,204690,46654,654591,973793,775432,670027,706648,53485,806321,610517,952018,759931,418539,484919,665012,902749,347817,976348,706618,988418,836386,328189,998771,538166,147796,329364,448625,758761,598807,525323,675564,835270,133460,810531,888382,903527,254570,51006,349648,436330,702159,928043,366307,930937,844361,915775],[565178,406336,795692,870641,794357,234951,923486,664708,503664,277717,431835,315458,287171,516504,426194,400424,106527,366489,687880,691685,680670,125244,636335,441802,441144,596682,284897,796280,447863,424880,313163,679191,872474,288808,363332,147805,985974,814429,280083,297816,230465,59942,593371,901214,318904,308999,28668,977024,361136,124583],[299518,478704,41407,84771,953254,815003,370266,524132,781511,416371,251354,131936,142434,330081,908610,203408,881996,73607,759092,597911,862927,464733,699845,512355,960307,729140,129483,607745,288828,936934,863926,220634,262035,293526,628490,811771,299282,613755,701929,910820,140492,135802,59043,523537,776683,744968,164961,275121,22615,321069],[391843,945885,982296,453518,981367,116604,366152,778879,813160,437621,222275,619577,904356,87900,509039,674256,435521,773193,241684,117292,262377,393414,639121,491279,767130,69679,24969,208678,489564,616460,376858,118851,684412,527735,286882,530646,157892,666095,671172,802025,603414,69998,869443,498383,675875,574778,588774,596709,824929,51411],[492273,182873,204180,257733,853692,192116,863548,885832,837651,995291,179029,180012,83712,762054,298479,345131,102007,278103,749694,148228,659033,885884,952428,490342,118798,798052,267251,805848,514003,983527,966605,672523,803117,571259,893803,95241,199992,634556,949776,439721,470712,357178,532703,631882,337239,645328,137963,285884,807599,127151],[754527,40231,944534,799740,108490,817697,850020,59151,178794,656186,790596,761145,509702,999045,682720,100284,292160,917573,443270,663837,446,271908,396275,935907,790237,638526,345491,386496,640125,447772,668976,885667,602803,511035,722844,601142,509115,513759,961135,760963,535641,397051,354187,331636,757416,664582,230226,728669,222705,197537],[518098,247539,470161,812731,721361,897086,426959,636580,223694,244372,798994,150658,759305,123564,737460,277763,307844,340529,629651,318742,891480,131758,564140,75921,832122,264524,890386,54632,207015,736162,81187,323496,686705,252842,881779,285995,471769,181616,267657,354608,140771,178795,453140,307278,248772,30713,743430,684028,119961,954365],[390778,624358,974262,416482,818049,1581,424810,642022,806606,47925,457616,76516,58766,753498,861434,654307,959576,634445,638004,374207,704666,212640,27181,260037,255974,586780,452368,909624,761623,272907,145072,984264,454661,987211,971148,301162,55174,185152,360303,181734,193407,793499,245391,585165,640876,290204,994148,576156,750828,250196],[158393,288519,100002,827923,854583,191140,623715,434095,599933,713573,831954,410854,451079,524749,809463,632482,140418,774475,669989,988012,201235,711569,930268,69502,451146,567804,545976,972831,744817,339246,881032,771041,561513,483137,536627,164682,71804,263605,545978,335814,568080,425027,326564,510714,445180,365530,294525,454624,559542,712960],[71884,625725,163451,356945,374589,857522,715646,570078,254816,77835,15027,831624,574085,720831,478390,29178,70462,873459,840413,563786,999428,445223,804045,883945,814987,158834,410223,900045,929541,850171,940476,772423,420671,879802,740415,238692,704693,529256,860151,149065,751638,108565,146540,156964,563014,332122,316737,248454,282178,282573],[765927,419416,859208,773541,423674,941515,440653,72288,960353,352326,955997,558483,303415,525297,60654,263820,899617,282115,379508,15668,273562,134635,334642,792187,462426,582594,584824,328471,292608,11045,466862,296434,490619,989480,933638,167258,398239,599852,725480,30430,560035,879034,880599,348344,102768,692205,236721,517642,602049,591707],[713141,993577,490887,494863,706187,919410,47687,590844,311277,718658,795317,846812,935853,389700,212057,50007,676139,607959,177327,313390,169184,489731,849733,864393,995734,359256,134964,614066,672714,467205,665387,825512,369629,81756,955041,133594,193103,45728,627137,10739,797323,962267,276814,944080,288061,179592,267301,229518,122318,945029],[28215,123035,400382,188208,945838,92465,100932,901278,689034,520282,91075,316994,382561,171860,390383,349228,394778,317920,958897,353740,827790,230330,824951,603350,388214,128830,60221,370510,919232,609773,487486,538010,370800,853151,229876,66947,162889,909728,413998,279728,773106,206309,729467,67102,846331,567711,47567,951134,128879,511370],[77219,383201,805728,244274,49171,775018,178430,686292,968130,543141,366308,173457,25457,167126,90594,889579,557976,762470,966205,350973,333086,292819,644223,634587,366811,998567,722560,745101,696617,261487,317609,167526,777344,54752,469760,793540,275064,758654,892308,630872,877533,151930,138668,557260,438650,432627,692340,690765,313208,647335],[6922,740164,985601,433741,350120,245130,329024,4943,419867,206256,80058,262970,899406,598289,982404,975766,380060,773560,8282,896848,696406,128274,344242,257687,811788,1016,962700,436495,290335,664441,747106,941725,13037,580061,953266,918086,945481,944378,930944,862913,487833,297873,292702,887671,421482,760312,546142,547357,518117,109986],[465841,881880,647054,814558,845488,92991,728741,472145,992677,452657,373404,457275,764543,116960,510494,42516,893368,857816,33133,393413,597154,548289,298093,29768,384424,801947,843082,939248,813787,460022,923581,244340,526127,165286,63113,320699,284443,382876,113192,190658,906598,926280,28469,442911,60520,905314,154788,866252,641052,222381],[686667,864257,138961,976522,662310,150560,141869,504994,169702,639767,348278,644008,950341,901472,937956,122699,141600,991665,336190,112845,189321,552019,654584,103234,602561,827683,425466,786669,370291,641423,955875,691666,450194,451842,521440,202298,455004,854778,94202,563578,478337,445172,601220,914795,318239,648154,628994,67187,889933,179917],[298004,754344,917179,471229,165026,470104,574098,689462,309078,349686,724134,472228,1146,518192,592336,951424,961297,20150,889352,66502,880869,547570,685878,343826,60069,871248,636296,458030,930102,571334,154830,786286,370043,2079,118256,698197,541494,354238,153793,693374,172912,866922,246509,452849,748046,268018,802649,911364,851834,153317],[524414,211068,208040,348964,863810,240554,806211,275299,294691,646525,281944,724190,290645,475895,475178,600692,170691,287770,384859,101908,991017,512964,45762,123782,92729,216009,344337,379172,478375,984336,1525,968285,86604,451977,74852,356816,311230,35473,597062,546754,300627,182764,388738,91980,261384,62203,791279,770282,654952,912470],[449143,771321,304544,75679,667217,264128,696039,106628,588883,77288,889746,515390,753136,347654,618218,953031,527894,432367,414164,665567,192427,735255,274833,240140,622773,879853,733510,473820,154678,292289,721668,480220,892656,863186,784342,506093,608850,688402,366623,816947,134891,968776,139226,843569,572238,958233,568386,3051,465380,904546],[555345,538449,50960,747412,607918,877772,840067,210617,224765,468437,83209,321766,706214,172971,558764,970338,480171,897655,844440,498393,418441,135719,948920,495042,945604,465132,616929,627943,752143,470741,520979,753118,413247,729458,131818,601898,598880,640375,410188,722268,375181,711016,57908,659857,305050,817378,331094,730437,108511,138966],[469709,308695,100133,717756,962350,642230,817002,324484,206939,613118,703898,481546,686060,296829,593479,673525,536746,1043,741453,595993,41108,736207,553497,973441,140872,541890,702030,126969,631620,468578,660046,310437,119681,545739,550792,28612,356943,754329,372239,149932,702440,625368,196131,864959,531875,706154,233045,461490,870249,447133],[529838,236433,573482,735659,221572,211591,47034,71191,464392,213595,976727,69108,153536,397534,762201,265856,938719,13852,436756,47805,926628,719136,474571,58623,847710,382215,511996,717037,289814,224160,983772,317694,720748,903993,871949,803623,687353,534499,714866,993983,98965,358535,687675,528323,245642,489232,128793,397816,62048,693397],[585753,641386,681726,704446,125424,414841,956387,519067,408298,33962,744569,288495,27003,491611,9250,987615,399551,971381,424908,464185,211589,982626,398673,683543,381994,524918,289502,936110,938110,452940,581839,926779,324921,428789,775502,684844,189278,847317,105684,666874,583738,774385,470079,198397,87010,537538,92376,66183,218608,434984],[109033,477388,976464,977638,305887,130130,896382,23009,65637,416508,913481,716268,363611,448523,707584,85225,33403,919139,398941,221052,798089,332931,718076,63066,518740,709315,45096,583146,717557,156809,858939,784372,719925,349427,32479,584016,864893,702587,104310,623381,32869,337957,745037,344538,214101,472390,291137,82233,511570,239916],[718111,843136,189026,758821,11456,852988,399579,529812,868884,160919,625702,853954,425735,960921,111515,880239,390523,448303,301790,169407,567429,580560,479311,750579,760941,773260,333688,940250,920257,218800,90307,134305,730887,2841,612760,234602,43459,533394,533647,54534,74357,105098,811874,952904,348631,522961,894509,156546,972027,34360],[469374,980458,217645,905203,837492,518266,992096,16899,437146,133,662112,927556,992977,101412,419981,744300,400340,285799,990307,908464,521765,328966,431439,822769,349449,580227,551350,805286,925408,205390,95238,342140,582695,80927,146429,952959,503988,199939,269914,426072,692866,678474,451641,135376,656182,456898,100872,163993,448573,319329],[270817,199371,510644,644139,104684,322235,474503,404879,806358,17886,972297,43599,891993,608168,858196,253846,359906,343689,445970,931786,192492,817496,347959,563622,242894,350217,770640,356404,988709,431982,860434,12202,372543,738989,768916,217900,93912,275570,386351,439364,154548,794503,811207,151528,945662,61514,511445,328600,36155,42413],[56488,249855,593165,878573,659777,318366,175997,616774,145713,837490,729848,9529,482386,76910,494874,335591,315617,778262,373851,33218,56597,38351,153464,300625,929798,541315,280278,312150,5518,394061,155648,869664,127625,330214,236077,724559,260576,88837,96366,336870,848229,960578,913975,94510,198084,408278,27112,673414,28055,425522],[522674,36122,893830,57340,214173,538543,178326,376671,63785,191675,65585,521290,930462,317409,433276,58254,163938,163092,545988,804651,547935,98865,709969,536232,206735,387413,374122,130105,558343,682534,615300,757545,116587,729575,664496,382534,278504,481605,842359,256176,364303,627642,398418,13204,661740,230013,820343,357619,368778,754238],[801723,395313,32107,348876,130252,15314,101656,111791,851990,47617,353097,769487,244627,665162,373159,650895,992159,151217,751964,988070,333620,544315,100984,136530,970434,991470,200602,605194,505755,191464,724165,668151,257122,190394,588936,127670,800373,106925,507485,538043,266992,386308,683458,725878,380206,801731,125242,310109,659169,111360],[514040,86345,614441,618838,77162,991024,518803,133158,460173,853464,997887,342450,649554,455398,421957,403607,61890,968534,667199,712868,333941,680229,735371,120636,7953,333278,7187,707392,400243,89589,245439,670107,508086,203201,507695,169405,219034,855,653855,269329,955143,721149,445361,901584,641882,595854,179522,542345,53522,776480],[831126,438901,323123,531312,495222,891387,554059,68055,532695,714269,108179,195199,227417,32093,638038,25245,666485,497533,203909,533975,930671,606400,177568,708073,40890,66330,600233,822141,750588,499330,680202,442667,722596,820352,820582,737807,492465,116692,231000,534075,833729,60785,230760,263730,336175,519311,43533,444862,251820,619761],[549072,531949,258816,110134,847464,751036,718105,539537,927514,803576,834183,445769,71658,315934,266891,956392,375025,901668,483702,681362,323253,613128,768851,807751,179480,54325,773362,102342,744133,247597,244536,141556,207831,918416,147414,911958,78338,814097,67269,20944,555808,496926,695915,994396,947426,732521,212127,438200,905944,493913],[51401,285358,562594,371226,638098,621921,978792,107379,492850,19398,244552,132730,968276,356656,724275,710982,439792,777192,334125,471037,953586,22147,322473,934761,390772,210612,39542,268078,441498,22458,933985,320087,953084,846538,22642,560805,559148,147196,429167,600938,927558,514260,445861,753317,536879,767977,854148,425696,418087,475882],[431544,405491,96936,627952,902008,789163,92340,858673,609587,276967,953125,813090,978950,877760,889464,511756,256978,936352,221777,332758,301730,648234,913959,353451,293367,371005,526676,631118,832648,821112,783691,202532,533140,855309,508465,754907,969297,816533,336800,547221,246135,988463,818851,483906,915280,967427,139090,504344,501469,582523],[768945,428910,351377,61880,810072,709466,161268,501534,790780,772788,688429,261766,460835,999587,73744,474429,612893,971684,124557,179111,426261,188480,555318,760176,566297,378671,114572,48394,464737,596617,677560,721206,128706,283897,595061,58582,950344,15137,7317,953299,284741,909124,504510,714012,812422,640982,205182,198969,321321,378215],[955708,194656,410327,416817,323928,759150,623061,545829,899359,666636,159380,660249,216419,65472,137924,131612,291451,889137,936481,242799,713689,910782,671805,252891,741733,102351,236706,907798,634341,244626,32122,668647,933785,32022,486314,157157,221744,624702,195529,701142,807381,172425,476362,149575,843624,423563,202430,758838,624841,681740],[820065,479205,748472,932059,906215,563367,324528,532609,800886,51666,639844,291475,578323,382918,558357,521675,610913,701429,627819,897425,185837,31426,473094,206733,63632,144959,567185,177572,411371,7826,132901,218541,12454,630895,90198,524525,363451,821738,61504,691793,658457,675519,203524,793477,191857,633763,466845,439495,541383,150017],[400321,397281,793837,449107,257939,707400,591562,440318,523968,199352,98334,789925,363822,862516,652466,655904,842972,738350,787051,808565,188020,736399,488172,566439,59388,780998,339567,675460,413681,955869,580894,980773,43983,665777,960058,635690,706781,509155,345266,671518,762923,331893,919233,114441,796524,431992,72026,165995,73781,422246],[634823,459185,424194,481549,917142,645406,671580,586236,436772,382914,772750,360215,4905,954402,997759,478134,930457,972216,982508,651934,357948,489630,401873,491554,260690,324167,235349,771736,994033,459235,550699,300481,923670,370393,48347,85955,168669,955034,13156,993467,583969,685310,578876,932373,239874,34239,506872,997315,509660,421978],[851679,652571,636501,206135,614064,807739,128661,657654,855801,850584,626077,337056,323541,140652,665690,655058,303693,801986,449506,835793,132373,173843,336610,952379,713807,766733,422559,481272,27281,562755,381977,822137,891751,709828,49704,737028,844672,84499,190565,659908,725875,181921,69145,168916,857387,74202,212508,947786,830265,650808],[66713,780141,688862,51634,257335,916960,439766,686796,239304,302175,368343,330949,760118,106442,397449,332225,119427,557131,849820,537269,856046,390727,652736,73719,331989,897708,192558,741181,369148,52919,900925,305347,739449,902851,404096,344118,160096,891691,885766,423065,574589,980959,659790,250895,276247,913807,603100,232036,914693,193209],[71684,607786,706423,364999,516983,147755,2762,197054,271159,447189,911138,384197,188780,693247,312438,71707,942197,122530,803519,709055,850087,487105,11562,469710,96021,416107,157844,60024,966085,208069,815316,705904,567399,277623,5463,817805,683339,241153,731943,723973,552204,551649,146647,231977,8626,23864,75842,836612,139790,357920],[589467,39713,278019,731484,96150,554741,789170,94776,208572,700970,540130,402451,828425,523774,681944,790060,669743,811790,811137,532523,406263,528980,614043,528140,287492,416476,799283,19879,625826,234715,696618,935264,142785,877251,761775,867528,216055,545002,498248,248748,582321,865392,826538,959716,412523,562216,993504,865766,873718,955482],[72773,247216,987615,851030,926389,475269,666717,578649,953611,399943,253023,380665,64361,562708,904583,488539,11076,517730,541048,344453,705251,490758,818544,961077,869440,857127,234868,419147,150420,515751,92015,272208,775206,643648,429243,343511,423266,97090,708791,235428,514691,944243,494667,979049,456916,214171,851333,27770,265251,632839],[127509,851507,645416,60754,246590,688198,867867,530249,411138,728064,472716,943519,988240,843215,594158,955745,565414,890145,658590,724628,534576,707662,657604,889650,159210,642806,757998,421438,670034,646658,496991,87638,611344,317960,391436,484616,221350,215575,408993,775262,648596,184506,840731,188748,139527,489271,801258,64505,358877,815530],[169329,137995,150293,549927,351587,180919,293289,250735,864696,30947,832241,550294,49683,365414,546404,767069,565182,987180,945480,273924,981470,128856,370231,355325,176741,254857,936270,330992,641061,918316,41420,683297,573165,181867,432421,736484,68131,719800,121282,802952,363725,858522,409580,458448,971015,978156,880426,387636,271835,585192],[738393,601330,227106,487887,91710,917048,447654,300811,180082,875266,887307,58136,793175,549322,216144,968979,981754,78770,70014,41011,660497,646889,480992,194789,83964,626934,324000,484445,556339,317252,248136,186582,519721,255338,282721,411948,891800,505643,768311,533880,376887,543615,479467,191900,93634,336418,990096,201555,40710,947080],[571277,706667,741334,654363,396293,502055,284319,679370,943282,288103,374965,398639,344606,335238,234490,630275,270107,775325,86087,358252,475391,121266,852372,890005,695853,326567,706945,824777,324576,312275,158832,537265,233067,239169,878458,233136,720487,344805,270184,90387,556578,562062,156054,45520,81198,777516,583986,598109,987863,539324],[179183,610784,304341,968822,320416,729659,319232,342634,27423,34919,963798,879873,870768,799086,454936,87281,784940,495522,863945,963777,400810,778960,647889,247334,560670,966294,197102,11377,929343,522553,915561,982050,377259,825386,170133,922117,159666,305071,818481,131391,533498,901245,753134,890676,289753,93217,720726,67588,554500,494914],[36429,543414,214389,222065,550339,620671,294707,371302,552619,371418,826596,625697,669796,316945,793313,340329,305241,512927,742916,87937,315489,471582,732343,720543,386864,291462,468524,511769,259893,606124,590088,632470,862399,540338,100771,959115,329173,450273,629292,151982,385198,65870,126036,586046,523660,266441,552614,866343,16977,708148],[779412,108138,655403,146446,538895,334717,898190,92068,146701,613341,613350,400833,370068,986180,807573,70454,392441,230016,660901,587521,37098,409479,973169,888991,833757,691988,499043,296871,579994,48902,271561,950869,213705,671250,791283,644416,557960,276217,373634,918153,8755,214067,225176,1440,227281,103611,700772,663080,216183,199257],[862705,928421,117323,904221,557035,981190,564213,759921,185659,532265,952898,409829,107340,724574,200575,927552,13241,27095,753354,109829,288086,694445,660919,873856,736253,702275,479933,527206,883248,73091,717274,530090,689396,373892,107116,705693,286005,534419,460039,718943,212951,56995,306986,236435,226919,996363,177377,779320,856068,508508],[881772,892722,597839,564641,470269,666802,293201,282895,850857,845133,186919,947568,238535,428130,193135,122235,503143,876564,395301,67017,452960,580406,817694,155230,844043,879793,10884,883102,574907,830900,447530,888316,443574,750604,509939,135644,543228,987531,369031,490880,871594,861485,664428,717133,123938,981040,422068,942525,433910,570373],[454821,889240,253645,270163,845798,785439,898781,673409,98200,567855,238790,844968,534359,242105,947197,204524,363771,981360,947972,799486,454913,424509,938866,454665,102658,311967,172072,900995,724007,584417,741320,320902,104139,611894,599239,868501,967637,579274,719548,10649,137074,892568,761862,669399,417321,988237,650349,6995,10053,82206],[541677,223833,55528,297687,146834,353668,422287,338603,776172,246332,836364,695132,483642,20347,743867,64601,979328,608058,525476,100934,131865,964358,868593,63020,529334,691722,525898,702763,382171,770835,611273,367952,24606,146731,60801,233414,671001,377173,522890,201068,532580,827548,125939,776814,762754,206739,251171,153454,948757,40588],[530992,772188,508022,808252,625770,751866,844474,988992,621334,223470,556732,152290,498684,793125,68422,90148,417400,474236,104438,358418,650697,893634,803656,816771,326985,991005,359496,442915,303359,941955,171478,662625,517623,581745,771933,349018,133726,995131,510464,822589,21973,28203,968085,749287,539402,611663,872838,766030,629364,543516],[695614,506101,826144,918155,622466,515360,686325,872482,775256,419673,966305,757738,138423,590712,786713,649191,920384,67351,830913,8229,667815,835329,257411,19820,863226,455924,8005,65023,456091,962088,217072,991926,274176,392246,192725,534794,368229,528380,731701,473864,120419,786570,521827,476013,451802,99078,920444,717919,508899,746730],[964229,28614,153352,301186,745734,230886,309721,82667,791714,311122,762140,552676,776644,728787,707157,965357,474500,495953,313632,716563,791447,150367,439806,621982,225058,783016,921800,194032,970307,803950,597076,450016,300676,571901,481569,414710,166481,826298,61486,566186,730663,734090,136838,863750,454736,683503,419522,780895,572335,688156],[811757,945725,282468,112469,426113,732118,824832,27732,581339,738792,933035,24617,930750,657274,710169,567185,427708,415054,420217,276215,584787,227521,712626,962911,869507,522264,742547,19728,524193,976311,933876,770774,421743,722065,382619,83045,27336,983407,648619,886000,875170,212496,717483,590532,794447,244731,314813,406961,309861,205470],[219378,345121,27491,966964,432174,37441,228853,307094,418681,868471,30032,206099,213740,37484,403138,73467,449279,887817,13744,419174,435358,820235,280744,385277,422925,18618,529818,529464,610634,15034,102503,380343,987197,326228,603048,381894,489383,537677,883786,757656,377313,338133,459620,15105,164173,467936,255555,657299,623701,780223],[818237,80139,216943,910552,476620,105387,490857,935405,166465,452429,64826,45262,648760,863815,569750,378564,667829,117546,697758,93558,744924,313684,518459,427239,429935,728058,871231,663480,294582,441520,347978,813193,594203,306543,861392,210949,896688,168587,698506,205670,475195,502111,684424,42803,46202,766038,526344,705498,316393,535454],[542532,815063,125052,295625,934707,235651,270343,286386,472262,19108,873949,136099,605766,831854,592450,384202,775203,18806,245702,210741,903706,734709,316466,305279,302508,873166,917499,598264,917782,763037,823664,182117,326413,488025,76320,781104,406241,546720,78045,12572,80007,706245,977707,56846,332142,678054,171229,269272,903105,6727],[503246,986219,723246,44083,386564,648776,894896,639877,302200,167941,14398,216657,148260,770238,490559,224159,357873,474728,823462,758122,600292,673328,701748,706141,689354,743772,88449,332019,292964,453902,196854,16790,17656,518324,989690,600471,511843,953144,507895,848952,677682,514069,245074,738117,380856,659882,288728,11777,559141,832414],[657686,62645,584619,17783,496019,447588,615807,429226,623785,727407,943925,542649,761253,202752,349459,57329,839166,357814,898832,790631,14819,228400,478814,789901,822543,426764,15159,587039,98098,569614,998092,51991,34079,164828,421149,992912,900583,121207,502360,110118,625440,408518,320419,639202,641677,944808,271184,922587,840423,618157],[750468,666201,173143,486086,638306,875228,279823,830621,96154,787559,718948,237841,652288,670455,821777,762728,618932,318216,887499,379453,532568,553372,731902,157198,590578,564565,669517,644910,397804,83990,893452,108527,62662,373092,385884,705693,725123,387114,573417,782203,569541,262182,588310,552899,934485,836129,945898,574316,899880,37653],[197317,345948,181121,382705,942794,194941,370525,810966,414179,1352,543417,655670,953099,150615,171968,536009,467768,331443,291131,988258,54698,540817,187320,641934,459947,668852,118521,990035,712176,612838,766762,799506,928153,900518,829082,691805,95795,442252,44204,765150,74453,407926,987207,976357,219354,911832,592206,700368,465296,42136],[468590,594256,376324,140625,50564,562557,673023,899346,498162,686622,517362,144283,846618,447987,451695,995769,6185,301376,561722,237285,523974,766071,221812,360777,706936,98141,220216,884972,428768,499729,692272,556010,38134,267564,904578,222176,652706,404403,621225,827705,744223,759579,704694,121291,947251,987732,827033,272824,425204,794207],[77367,143593,260862,849087,691054,54608,609245,158417,707388,815127,475597,784016,364067,371708,394236,103153,791399,265250,388241,490977,654206,238798,452700,631664,497639,856969,919985,770310,341498,941356,391714,293087,699400,962968,866982,480356,673353,999347,909593,976474,176613,999391,524417,809549,230306,281159,226723,933249,580995,278685],[166017,811509,517082,337713,889149,591802,405872,279353,898534,636305,506853,553766,885928,372415,600499,256780,608171,843873,324677,599249,405404,642074,99425,195703,926234,300829,397786,983904,566000,749283,558927,532501,585244,339836,397829,365143,593953,92033,810435,730943,979768,330497,755169,535785,377296,746099,21547,288577,251693,601609],[731166,223430,675753,959365,83302,110008,697595,282360,556574,708754,645636,470866,964546,252322,402454,263817,688223,558026,15704,845533,290683,852373,894697,670602,788088,305352,365272,225049,617683,680997,82953,396780,695188,122044,384575,635646,864303,994518,718082,910931,144552,316350,445386,82323,924815,648157,459604,377965,813853,38969],[763841,365818,759537,847157,72036,530709,894465,282296,355937,638554,882983,103853,630449,455983,468927,244441,320775,319032,270796,102260,353012,506668,90364,386549,925326,986281,171192,140817,767089,818603,449508,787462,15504,799338,141363,280804,635811,84855,206244,193684,967995,46998,454578,665993,949087,650701,450801,116084,612354,947278],[880228,494501,753175,287888,880006,537575,724050,762236,543549,113324,540115,376763,389730,566124,914004,522193,446305,176189,768003,142107,363832,554933,881912,781619,829563,615208,536604,960980,914484,282482,993691,974178,394699,223770,990662,347380,853815,955748,949257,896011,711327,569494,291623,399565,549602,239172,768875,99102,201970,922413],[17520,458784,349090,421175,862164,70663,555740,696540,773537,62513,834377,724959,766385,477209,290824,815030,414040,302017,796462,485540,153895,408813,530797,971448,717087,338827,426605,35418,615144,766467,353266,590507,719008,898976,394849,255223,289735,26263,71821,178091,714053,596563,330201,776233,733740,833023,501301,363451,371701,752734],[751968,724799,904851,649756,783690,387656,747710,170373,405847,296707,422481,657629,75018,473252,290904,452248,936998,107682,674056,799101,880403,364221,560931,805398,898768,20362,979656,962492,90496,351708,824773,112688,105689,442146,859544,170371,392263,963695,305072,862479,269510,937768,800397,668735,661401,128695,248787,664045,891532,511550],[944715,96726,311034,174352,416877,125797,217761,470839,945254,561914,381775,722063,369864,870098,843900,64024,315305,874161,950765,649028,859412,88084,870385,364876,891523,422860,251779,502914,265940,588323,755997,365032,4702,280414,310266,65002,986760,724541,135669,829597,882778,56527,603557,681901,773823,181298,108009,640154,709210,252805],[208876,315767,901201,763660,975280,959927,279566,744950,542178,789498,162692,74474,752421,647630,240543,355076,717419,929450,165167,29694,416383,593617,132893,712386,195978,966221,297501,912859,788535,744331,404914,60833,397373,871134,829264,548682,135397,843707,210285,34467,786461,551964,371372,722990,332341,444320,914252,623518,963640,606874],[401923,710410,737055,673118,306750,918553,213205,129176,851338,833784,602459,338595,407667,499362,137569,489048,293744,794194,714300,105935,857965,458064,601837,433762,378778,925427,400817,284164,354675,235715,153450,676885,479829,512324,642984,350233,644439,858644,567715,280106,994127,592276,686026,851533,435165,358657,488520,947528,892178,709131],[493825,867719,522421,900246,134280,513882,523024,908734,595608,10601,567680,517100,155242,664961,197809,210082,406254,514563,45693,571921,256822,330030,554446,630716,321726,831858,335492,866312,248506,22627,847089,570484,916055,112784,390183,326187,571372,709412,788228,757574,984362,594055,175309,426515,313566,245666,358615,795566,614073,291768]]], // 381458
];

include_once dirname(__DIR__) . DIRECTORY_SEPARATOR ."xhprof.php";
$xhprof = new Xhprof();
foreach ($datas as $data){
    // var_dump($data);

    $obj = new Solution();
    $result = $obj->minimumEffortPath(...$data);
    // $result = $obj->($xhprof->tree($data));
    // $result = $obj->($xhprof->listNode($data));
    // $result = $obj->find(...$data);
    var_dump($result);
    // if(count($result)<=20){
    //     var_dump($result);
    // } else {
    //     var_dump(count($result));
    // }
    echo str_repeat(PHP_EOL, 3);
    echo str_repeat("<br>", 3);
}

// foreach ($datas as $data){
//     $obj = new $data[0][0](...$data[1][0]);
//
//     for ($i=1; $i<count($data[0]); $i++){
//         $result = $obj->$data[0][$i](...$data[1][$i]);
//
//         echo $data[0][$i] ."(\"". implode(",", $data[1][$i]) ."\") ";
//             if($result === true){
//                 echo "True";
//             } elseif($result === false) {
//                 echo "False";
//             } elseif($result === null) {
//                 echo "Null";
//             } elseif(is_array($result)) {
//                 var_dump($result);
//             } else {
//                 echo $result;
//             }
//         echo PHP_EOL;
//     }
//
//     echo str_repeat(PHP_EOL, 3);
// }
$xhprof->end();
